package com.algorithms.brownian.pq;

import java.util.Comparator;
import java.util.Iterator;

public abstract class AMaxMinPriorityQueue<Key> implements Iterable<Key> {

	private Key[] pq; // store items at indices 1 to N
	protected int N; // number of items on priority queue
	protected Comparator<Key> comparator; // optional Comparator

	/**
	 * Initializes an empty priority queue with the given initial capacity.
	 * 
	 * @param initCapacity
	 *            the initial capacity of the priority queue
	 */
	@SuppressWarnings("unchecked")
	protected AMaxMinPriorityQueue(int initCapacity) {
		pq = (Key[]) new Object[initCapacity + 1];
		N = 0;
	}

	/**
	 * Initializes an empty priority queue.
	 */
	protected AMaxMinPriorityQueue() {
		this(1);
	}

	/**
	 * Initializes an empty priority queue with the given initial capacity,
	 * using the given comparator.
	 * 
	 * @param initCapacity
	 *            the initial capacity of the priority queue
	 * @param comparator
	 *            the order in which to compare the keys
	 */
	@SuppressWarnings("unchecked")
	protected AMaxMinPriorityQueue(int initCapacity, Comparator<Key> comparator) {
		this.comparator = comparator;
		pq = (Key[]) new Object[initCapacity + 1];
		N = 0;
	}

	/**
	 * Initializes an empty priority queue using the given comparator.
	 * 
	 * @param comparator
	 *            the order in which to compare the keys
	 */
	protected AMaxMinPriorityQueue(Comparator<Key> comparator) {
		this(1, comparator);
	}

	/**
	 * Is the priority queue empty?
	 * 
	 * @return true if the priority queue is empty; false otherwise
	 */
	public boolean isEmpty() {
		return N == 0;
	}

	/**
	 * Returns the number of keys on the priority queue.
	 * 
	 * @return the number of keys on the priority queue
	 */
	public int size() {
		return N;
	}

	public void insert(Key key) {
		if (size() >= getLength() - 1) {
			resize(2 * getLength());
		}
		pq[++N] = key;
		swim(N);
		assert isHeapValid();
	}

	@SuppressWarnings("unchecked")
	protected void resize(int capacity) {
		assert (capacity > getLength());
		Key[] copy = (Key[]) new Object[capacity];
		for (int ii = 0; ii <= size(); ii++) {
			copy[ii] = pq[ii];
		}
		System.out.println(pq.length);
		pq = copy;
	}

	@SuppressWarnings("unchecked")
	protected boolean less(int i, int j) {
		if (comparator == null) {
			return ((Comparable<Key>) pq[i]).compareTo(pq[j]) < 0;
		} else {
			return comparator.compare(pq[i], pq[j]) < 0;
		}
	}

	@SuppressWarnings("unchecked")
	protected boolean greater(int i, int j) {
		if (comparator == null) {
			return ((Comparable<Key>) pq[i]).compareTo(pq[j]) > 0;
		} else
			return comparator.compare(pq[i], pq[j]) > 0;
	}

	protected void setValuAtPos(int i, Key value) {
		pq[i] = value;
	}

	protected Key getValueAtPosition(int i) {
		return pq[i];
	}

	protected int increaseSize() {
		return ++N;
	}

	protected int decreaseSize() {
		return N--;
	}

	protected int getLength() {
		return pq.length;
	}

	protected void checkSize() {
		if (N > 0 && N <= (pq.length - 1) / 4) {
			resize(pq.length / 2);
		}
	}

	protected void exch(int k, int i) {
		Key key = pq[k];
		pq[k] = pq[i];
		pq[i] = key;
	}

	/**
	 * Returns an iterator that iterates over the keys on the priority queue in
	 * descending order. The iterator doesn't implement <tt>remove()</tt> since
	 * it's optional.
	 * 
	 * @return an iterator that iterates over the keys in descending order
	 */
	public abstract Iterator<Key> iterator();

	protected abstract class AHeapterator implements Iterator<Key> {

		// create a new pq
		private AMaxMinPriorityQueue<Key> copy;

		// add all items to copy of heap
		// takes linear time since already in heap order so no keys move
		public AHeapterator() {
			initComparator();
			for (int i = 1; i <= size(); i++)
				copy.insert(getValueAtPosition(i));
		}

		protected void initComparator() {
			if (comparator == null)
				copy = createHeap();
			else
				copy = createHeap(comparator);// new MaxPQ<Key>(size(),
												// comparator);
		}

		protected abstract AMaxMinPriorityQueue<Key> createHeap();

		protected abstract AMaxMinPriorityQueue<Key> createHeap(
				Comparator<Key> comparator);

		public boolean hasNext() {
			return !copy.isEmpty();
		}

		public void remove() {
			throw new UnsupportedOperationException();
		}

		public abstract Key next();

		public Key delete() {
			return copy.delete();
		}
	}

	protected abstract boolean isHeapValid();

	protected abstract void swim(int k);

	protected abstract void sink(int k);

	public abstract Key delete();
}
